package Algorithm.BST;

/**
 * 现给定一组数据，请你对这组数据按给定顺序建立一棵排序二叉树，并输出其中序遍历的结果
 * @author chenjunjie
 * @since 2018-04-03
 */
public class BinarySortTreeTest {

    /**
     * 向bst这棵树中插入数据为v的节点
     * @parma bst 这颗树
     * @parma v 数据值
     * @return
     */
    public BinarySortTree insertBST(BinarySortTree bst_root, int v){
        if(bst_root == null){
            bst_root = new BinarySortTree();
            bst_root.data = v;
            bst_root.lChild = null;
            bst_root.rChild = null;
        }else {
            if(bst_root.data > v){
                //递归插入左子树
                bst_root.lChild = insertBST(bst_root.lChild, v);
            }else {
                //递归插入右子树
                bst_root.rChild = insertBST(bst_root.rChild, v);
            }
        }

        return bst_root;
    }

    /**
     * 删除bst这棵树中数据为v的节点(所有节点)
     * @parma root 这颗树，表示根点
     * @parma v 数据值
     * @return
     */
    public boolean deleteBST(BinarySortTree root, int v){
        if(root == null){
          return false;
        }

        BinarySortTree parent = root;
        BinarySortTree cur = root;
        //定位到需要删除的节点
        while(cur !=null) {
            if (cur.data > v){
                parent = cur;
                cur = cur.lChild;
            } else if (cur.data < v){
                parent = cur;
                cur = cur.rChild;
            } else  {
                // 只有一个右节点, 右子节点直接连接父节点
                if(cur.lChild == null && cur.rChild != null) {
                    parent.rChild = cur.rChild;
                    cur = cur.rChild;
                } else if(cur.rChild == null && cur.lChild != null) {
                    //只有一个左节点, 左子节点直接连接父节点
                    parent.lChild = cur.lChild;
                    cur = cur.lChild;
                } else if(cur.lChild == null && cur.rChild == null) {
                   if(parent.data > cur.data) {
                       //删除左边
                       parent.lChild = null;
                       cur = null;
                   }else if(parent.data <= cur.data) {
                       //删除右边边
                       parent.rChild = null;
                       cur = null;
                   }
                } else if(cur.lChild != null && cur.rChild != null) {
                    //左右节点都有
                    //BinarySortTree temp = searchMin(root.rChild); //这种方式找不到父节点，不好进行交换
                    //采用非递归的方式
                    BinarySortTree temp = cur.rChild;
                    while(temp.lChild != null){
                        parent = temp;
                        temp = temp.lChild;
                    }
                    cur.data = temp.data;
                    parent.lChild = null;
                }
            }
        }

        return true;
    }

    /**
     * 查询bst这棵树中最小节点
     * @parma bst 这颗树
     * @return
     */
    public BinarySortTree searchMin(BinarySortTree bst){
        if(bst == null) {
            return null;
        }
        if(bst.lChild != null) {
            //一直往左孩子找，直到没有左孩子的结点
            bst = searchMin(bst.lChild);
            return bst;
        }

        return bst;
    }

    /**
     * 查询bst这棵树中最大节点
     * @parma bst 这颗树
     * @return
     */
    public BinarySortTree searchMax(BinarySortTree bst){
        if(bst == null) {
            return null;
        }
        if(bst.rChild != null) {
            //一直往右边孩子找，直到没有右孩子的结点
            bst = searchMax(bst.rChild);
            return bst;
        }

        return bst;
    }


    /**
     * 中序遍历这颗树(本测试里通过中序遍历打印的即为排序的数字)
     *
     */
    public void mid_store(BinarySortTree bst){
        if(bst != null){
            mid_store(bst.lChild);
            System.out.println(bst.data);
            mid_store(bst.rChild);

        }
    }

    /**
     * 前序遍历这颗树
     *
     */
    public void pre_store(BinarySortTree bst){
        if(bst != null){
            System.out.println(bst.data);
            pre_store(bst.lChild);
            pre_store(bst.rChild);
        }
    }

    /**
     * 后序遍历这颗树
     *
     */
    public void after_store(BinarySortTree bst){
        if(bst != null){
            after_store(bst.lChild);
            after_store(bst.rChild);
            System.out.println(bst.data);
        }
    }



    /**
     * 测试入口
     *
     */
    public static void main(String[] args){
        BinarySortTreeTest opt = new BinarySortTreeTest();
        BinarySortTree bst = opt.insertBST(null,17);
        opt.insertBST(bst,7);
        opt.insertBST(bst,5);
        opt.insertBST(bst,3);
        opt.insertBST(bst,6);
        opt.insertBST(bst,14);
        opt.insertBST(bst,6);
        opt.insertBST(bst,16);
        opt.insertBST(bst,26);
        opt.insertBST(bst,32);
        opt.insertBST(bst,14);



        System.out.println("--------中序遍历----------");
        opt.mid_store(bst);
        System.out.println("--------前序遍历----------");
        opt.pre_store(bst);
        System.out.println("---------后序遍历---------");
        opt.after_store(bst);
        System.out.println("---------最大值---------");
        System.out.println(opt.searchMax(bst).data);
        System.out.println("---------最小值---------");
        System.out.println(opt.searchMin(bst).data);
        System.out.println("---------删除节点---------");
        opt.deleteBST(bst, 9);
        opt.mid_store(bst);



    }


}
